#include<iostream>
#include<vector>
#include<unordered_map>
#include <cstdlib>
#include<ctime>
using namespace std;

class RandomizedSet {
public:
	RandomizedSet() {
		srand((unsigned)time(NULL));
	}

	bool insert(int val) {
		if (indices.count(val)) {
			return false;
		}
		int index = nums.size();
		nums.emplace_back(val);
		indices[val] = index;
		return true;
	}

	bool remove(int val) {
		if (!indices.count(val)) {
			return false;
		}
		int index = indices[val];
		int last = nums.back();
		nums[index] = last;
		indices[last] = index;
		nums.pop_back();
		indices.erase(val);
		return true;
	}

	int getRandom() {
		int randomIndex = rand() % nums.size();
		return nums[randomIndex];
	}
private:
	vector<int> nums;
	unordered_map<int, int> indices;
};


int main() {
	RandomizedSet* obj = new RandomizedSet();
	bool param_1 = obj->insert(1);
	bool param_2 = obj->remove(2);
	int param_3 = obj->getRandom();
	cout << "Done" << endl;
	return 0;
}